Computed Tomography Colonography (CTC) or Virtual Colonoscopy (VC) is a minimally-invasive alternative to conventional optical colonoscopy to detect polyps of the colon wall. CTC has significantly evolved since then and is now emerging as a possible screening technique for colorectal cancer. The CTC technique combines computer tomography of the abdomen with specialized visualization techniques in order to provide the physician with 2D and 3D views of the colon targeting a complete coverage of the colon wall. Traditionally, 2D axial images synchronised with 3D rendered fly-through navigation of the colon is used for virtual inspection. The length of the colon and its convoluted nature, however, make such an inspection process tedious and error-prone. Moreover, a polyp, hidden behind a fold, can easily be missed with this approach.
Virtual colon flattening or virtual colon dissection is a recently emerging visualization technique for colon inspection. The virtual flattening is achieved by unfolding the entire surface of the colon to the 2D plane and imposing from the centreline-view lighting on the unfolded colon. The resulting view resembles pathological preparation or dissection of the colon, hence the name virtual colon dissection.
A popular approach to generate an unfolded view of the colon starts by uniformly sampling the centreline of the colon. This is followed by computation of a cross section at each centreline point using ray casting. Then, the unfolded view is obtained by unfolding and concatenating the obtained cross sections. Examples are described in U.S. Pat. No. 6,212,420 and US2002/193687. The main disadvantage of such a technique is that, in high curvature regions of the centreline, polyps may be missed or single polyps may occur multiple times. This happens because, at high curvature regions, the distance between neighbouring cross sections can become too large or intersections of neighbouring cross sections occur. Although several approaches have been introduced to overcome these problems, these approaches can introduce large distortions.
Colon flattening through surface parameterization is a technique that directly generates a guaranteed one-to-one flattening of the whole colon surface. In this way, polyps are never repeated or missed. However, known parameterization techniques either preserve angles or areas in the flattening process, and not both angles and areas. Angle preservation preserves local shape but it can result in significant down-scaling of a polyp in the flattened representation which, in turn, can result in overlooking of the polyp during inspection (Haker et al., IEEE Trans Med Imaging 19(7) (2000b) 665-670). The increased distortion resulting from strict area preservation, on the other hand, may also lead to difficulties in the detection of polyps.
Surface parameterization is a technique to convert a mesh, described using primitives like triangles, quadrilaterals, or polygons, into a parametric description of the surface. In most applications the surface is two-dimensional and it is embedded in a three dimensional space. Thus, a parameterization is a map from a two-parameter domain onto the three-coordinate surface.
Most research on surface parameterization has focused on planar and spherical parameterization because many real world surfaces are either of disc-like or spherical topology. Surfaces of other topologies are handled by dividing the surface in charts of disc-like topology and subsequently parameterizing these charts to the plane. The choice of the parameterization domain is imposed by the topology of the surface that needs parameterization. Since the parameterization should be a continuous map, the parameterization domain and the surface should be topologically equivalent. A class of surfaces that is much less covered but also widely encountered are surfaces of cylindrical topology.
Cylindrical parameterization constructs a map from a surface of cylindrical topology to the cylinder. The few methods that already exist to construct such maps, usually alter the topology of the surface prior to parameterization and often fail in keeping distortions within acceptable bounds. Some rely on a two step procedure involving cutting of the surface which may result in a suboptimum (see the Haker paper).
There has been little research in parameterization of surfaces of cylindrical topology (e.g. the above-mentioned Haker paper), although lots of surfaces of this kind are encountered in the real world: blood vessels, the trachea, the colon, cochlear canals, etc. Cylindrical parameterization can even be used for certain elongated spherical surfaces after topological modification.
Surface parameterization is a very useful technique. It is used in computer graphics for detail mapping, remeshing and level of detail construction, rendering acceleration and also morphing and detail transfer between surfaces. A parameterization is also very useful for describing surfaces using basis functions, which has applications in surface fitting, description and compression. In medical imaging, parameterizations are useful for easing the visualization of complex structures and they also allow the construction of surface correspondences which make statistical shape analyses and model based image segmentation possible. Applications of specific interest for cylindrical parameterization are segmentation and analysis of tubular structures, e.g. automatic shape guided segmentation of human trachea and non-invasive stent shape prediction for surgical intervention in tracheal stenosis. It has also been employed for mapping, segmentation and centreline calculation of possibly bifurcating blood vessels. Furthermore, cylindrical parameterization can be used for virtual flattening of the colon in virtual colonoscopy and prone-supine scan colon registration is also envisioned.
Linear parameterization methods, such as proposed by Haker et al. (IEEE Transactions on Visualization and Computer Graphics 6 (2) (2000a) 181-189, ISSN 1077-2626), are popular since they are very fast and generate parameterizations with low (angle) distortion in case the surfaces are well-behaved. Usually, the parameterization is obtained by solving the Laplace equation on the surface for both parameter coordinates while enforcing certain boundary constraints. Depending on the actual discretisation of the Laplace operator, different realisations of the system matrix are possible. Among the most celebrated are cotangent weighting, resulting in a harmonic map, and mean value weighting. Often, the boundary mapping of the parameterization is defined beforehand which thus results in a boundary value problem. Free boundary parameterizations, where the boundary of the parameterization is allowed to move freely together with the interior, are achieved using natural boundary conditions.
For cylindrical parameterization, a number of approaches have been proposed in the past:
Haker et al. (2000a) solve two boundary value problems in order to obtain a conformal parameterization of the surface. First, the axial parameterization is obtained. Then, the surface is dissected into a topological disc and a conjugate angular parameterization is derived.
Zöckler et al. (The Visual Computer 16 (5) (2000) 241-253) parameterized the cylindrical surface in two stages: first the surface is cut and parameterized onto the plane, and then the parameterization is glued back together and optimized on the cylinder. Since the surface is cut, distortions are introduced in the first optimization. Therefore the parameterization needs to be optimized a second time. For complex surfaces this method might not find the optimal parameterization.
The method of Antiga and Steinman (Medical Imaging, IEEE Transactions on 23 (6) (2004) 704-713, ISSN 0278-0062) maps segments of blood vessels to the cylinder by first mapping the axial coordinate using a harmonic function, similar to Haker et al. (2000b), and then mapping the angular coordinate using a heuristic method. Although this approach provides nice results for vessels, it can only be applied to surfaces of cylindrical topology with star shaped cross sections.
Grimm (International Journal of Shape Modeling 10 (1) (2004) 51-80) proposes a method to map surfaces to certain manifolds. For the cylinder manifold, the surface is first divided into a number of charts, which are then parameterized separately and stitched together. The parameterization is then relaxed along the chart boundaries to remove the high distortion. Unfortunately, this relaxation is only local and, therefore, the resulting parameterization can be suboptimal with respect to the distortion metric.
In Hong et al. (Proceedings of the 2006 ACM symposium on Solid and physical modeling, ACM, Cardiff, Wales, United Kingdom, ISBN 1-59593-358-1, 85-93, 2006), a parameterization of the colon is obtained using holomorphic one-forms on a dual covering of the colon surface. They obtain similar results as our linear method but at the expense of duplicating surface geometry for the double covering. Furthermore, positional landmark constraints can only be satisfied using a second optimization, as opposed to our method, where they can be directly incorporated.
Consequently, there is a need for improved techniques for surface parameterization, more particularly cylindrical surface parameterization, that minimize and balance both angle and area distortion.
The paper “Parameterisation of Tubular Surfaces on the cylinder” (T. Huysmans et al., Journal of WSCG 2005, vol. 13, January 2005, pp. 97-104) discloses a method to parameterize tubular surfaces on a cylinder. However, as recognised by the authors on p. 102, the proposed solution wherein the length of the cylindrical domain has to be estimated by the user of the method.
Hence, there is also a need for an approach wherein this length is determined automatically.